/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
		ListNode* phead = new ListNode(-1);
		ListNode* tail = phead;
		while(pHead1 && pHead2)
		{
			if(pHead1->val < pHead2->val)
			{
				tail->next = pHead1;
				tail = pHead1;
				pHead1 = pHead1->next;
			}
			else 
			{
				tail->next = pHead2;
				tail = pHead2;
				pHead2 = pHead2->next;
			}
		}
		if(pHead1)
			tail->next = pHead1;
		if(pHead2)
			tail->next = pHead2;
		
		return phead->next;
    }
};


//合并K个已经排序的链表
class Solution {
public:
    struct cmp{
        bool operator()(ListNode* l,ListNode* r)
        {
            return l->val > r->val;
        }
    };
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        priority_queue<ListNode*,vector<ListNode*>,cmp> pq;
        for(auto node:lists)
        {
            if(node != nullptr)
                pq.push(node);
        }
        ListNode* head = pq.top();
        pq.pop();
        if(head->next)
            pq.push(head->next);
        
        ListNode* tail = head;
        while(!pq.empty())
        {
            ListNode* top = pq.top();
            tail->next = top;
            tail = top;
            pq.pop();

            if(top->next)
                pq.push(top->next);
        }
        return head;
    }
};


//从尾到头打印链表
//方法1:使用栈
vector<int> printListFromTailToHead(ListNode* head) 
{
    stack<int> st;
    ListNode* cur = head;
    while(cur)
        st.push(cur->val),cur = cur->next;
    vector<int> v;
    while(!st.empty())
        v.push_back(st.top()),st.pop();
    
    return v;
}


//方法2:逆置vector
vector<int> printListFromTailToHead(ListNode* head) {
    ListNode* cur = head;
    vector<int> v;
    while (cur)
        v.push_back(cur->val), cur = cur->next;
    reverse(v.begin(),v.end());
    return v;
}

//方法3: 递归
void process(ListNode* cur,vector<int>& v)
{
    if(cur == nullptr)
        return ;
    process(cur->next,v);
    v.push_back(cur->val);
}
vector<int> printListFromTailToHead(ListNode* head) {
    vector<int> v;
    process(head,v);
    return v;
}

//链表奇偶重排
ListNode* oddEvenList(ListNode* head) 
{
    if(!head || !head->next)
        return head;

    ListNode* oddHead = head;//奇数头
    ListNode* oddTail = oddHead;
    ListNode* evenHead = head->next;//偶数头
    ListNode* evenTail = evenHead;
    int size = 3;
    ListNode* cur = head->next->next;
    while(cur)
    {
        ListNode* next = cur->next;
        cur->next = nullptr;
        if(size % 2)
        {
            oddTail->next = cur;
            oddTail = cur;       
        }
        else 
        {
            evenTail->next = cur;
            evenTail = cur;
        }
        size++;
        cur = next;
    }
    oddTail->next = evenHead;
    return oddHead;
}